﻿
namespace Leetcode.N1305;
public class Solution
{
    public IList<int> GetAllElements(TreeNode root1, TreeNode root2)
    {
        var list1 = new List<int>();
        var list2 = new List<int>();
        this.ToSortedList(root1, list1);
        this.ToSortedList(root2, list2);
        return this.Merge(list1, list2);
    }

    private void ToSortedList(TreeNode node, IList<int> list)
    {
        if (node == null)
        {
            return;
        }
        this.ToSortedList(node.left, list);
        list.Add(node.val);
        this.ToSortedList(node.right, list);
    }

    private IList<int> Merge(IList<int> list1, IList<int> list2)
    {
        var result = new List<int>(list1.Count + list2.Count);
        var index1 = 0;
        var index2 = 0;

        while (true)
        {
            if (index2 == list2.Count)
            {
                for (; index1 < list1.Count; index1++)
                {
                    result.Add(list1[index1]);
                }
                break;
            }

            if (index1 == list1.Count)
            {
                for (; index2 < list2.Count; index2++)
                {
                    result.Add(list2[index2]);
                }
                break;
            }

            if (list1[index1] <= list2[index2])
            {
                result.Add(list1[index1++]);
            }
            else
            {
                result.Add(list2[index2++]);
            }
        }

        return result;
    }
}